/**
697. 数组的度
	给定一个非空且只包含非负数的整数数组nums，数组的度的定义是指数组里任一元素出现频数的最大值。
	你的任务是在 nums 中找到与nums拥有相同大小的度的最短连续子数组，返回其长度。
 */

package main

/*import "fmt"

func main()  {
	arr := []int{1,2,2,3,1,4,2}
	fmt.Println(findShortestSubArray(arr))
}*/

var intMax = int(^uint(0) >> 1)

func findShortestSubArray(nums []int) int {
	// 用于记录度的map
	degreeMap := make(map[int]*ArrayNode)
	// 设置数组的度的初始值为1，一个非空数组的度，一定是大于等于1的
	degree :=1
	// 初始化最小长度为int Max，当然也可以是原数组的长度，子数组最长也不会唱过原数组的长度
	minLength := intMax

	// 遍历原数组
	for i,val := range nums {
		// 当map已存在该值时，说明辅助节点的startIndex已固定，此时只需更新endIndex就行了，并使其size加1
		if node,ok:= degreeMap[val];ok {
			node.endIndex = i
			node.size++
			// 当size大于当前的度时，更新当前的度为size，并更新子数组的最小长度
			if node.size>degree {
				degree = node.size
				minLength = node.endIndex-node.startIndex +1
			}
			// 当size等于当前的度时，通过计算当前节点end与start index的距离，来更新最小长度
			if node.size==degree {
				if node.endIndex-node.startIndex+1 < minLength {
					minLength = node.endIndex-node.startIndex +1
				}
			}
			// 更新map
			degreeMap[val] = node
			continue
		}
		// 当map没有记录该值时，初始化一个辅助节点，只设置startIndex为i即可，endIndex设置为0，size设置为1
		newNode := &ArrayNode{i,0,1}
		// 添加节点到map
		degreeMap[val] = newNode
	}

	// 当数组的度为1时，说明该数组为不重复数组，子数组的最小长度为1
	if degree==1 {
		return 1
	}
	return minLength
}

// 辅助节点，记录相同数字的起始点以及最终点，和重复次数
// 在size（度）最大时，使endIndex-startIndex最小，这个最小值就是有相同度的子数组的最短长度
type ArrayNode struct {
	startIndex int
	endIndex int
	size int
}
